package 图.有向图;

import 抽象数据类型.Digraph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-01
 */
public class 有向图的可达性 {
    public static void main(String[] args) {
        int[] arr1 = {6, 0, 2, 0, 3, 5, 4, 4, 2, 2, 3, 6, 8, 7, 9, 9, 11, 12};
        int[] arr2 = {0, 1, 0, 5, 5, 4, 3, 2, 4, 3, 2, 4, 7, 8, 11, 10, 12, 9};
        Digraph g = new Digraph(arr1.length);
        for (int i = 0; i < arr1.length; i++) {
            g.addEdge(arr1[i], arr2[i]);
        }
        List<Integer> sources = new ArrayList<>(Arrays.asList(new Integer[]{0}));
        DirectedDFS directedDFS = new DirectedDFS(g, sources);
        for (int v = 0; v < g.V(); v++) {
            if (directedDFS.marked(v)) {
                System.out.print(v + " ");
            }
            System.out.println();
        }

    }

    public static class DirectedDFS {
        private boolean[] marked;

        public DirectedDFS(Digraph G, int s) {
            marked = new boolean[G.V()];
            dfs(G, s);
        }

        public DirectedDFS(Digraph G, Iterable<Integer> sources) {
            marked = new boolean[G.V()];
            for (Integer source : sources) {
                if (!marked[source]) {
                    dfs(G, source);
                }
            }
        }

        private void dfs(Digraph g, int v) {
            marked[v] = true;
            for (Integer w : g.adj(v)) {
                if (!marked[w]) {
                    dfs(g, w);
                }
            }
        }

        public boolean marked(int v) {
            return marked[v];
        }
    }
}
